// 分治法  先分再合起来

let arr = [2, 4, 7, 3, 5, 1]

function mergeSort(arr) {
  let len = arr.length
  if (arr.length <= 1) {
    return arr
  }

  // 找分割点
  let mid = Math.floor(len / 2)
  const leftArr = mergeSort(arr.slice(0, mid))
  const rightArr = mergeSort(arr.slice(mid, len))

  arr = mergeArr(leftArr, rightArr)   // 合并两个数组，依旧是有序的
  return arr
}

// 1 2 7 8 
// 3 5 9 

function mergeArr(arr1, arr2) {
  let res = []
  let i = 0, j = 0
  let len1 = arr1.length
  let len2 = arr2.length

  while (i < len1 && j < len2) {
    if (arr1[i] < arr2[j]) {
      res.push(arr1[i])
      i++
    } else {
      res.push(arr2[j])
      j++
    }
  }

  if (i < len1) {
    res = res.concat(arr1.slice(i))
  } else {
    res = res.concat(arr2.slice(j))
  }

  return res
}

console.log(mergeSort(arr));
